A product code is a multi-dimensional array of (n,k) linear block code that exploits a simple and relatively efficient method to construct more powerful codes using linear block code structures. FIG. 1 illustrates construction of a two-dimensional block product code, using a k1×k2 array of data to be encoded.
In the encoding, each row of k2 data values is augmented to include n2−k2 parity check bits for the data in that row; and each column of k1 data values is augmented to include n1−k1 parity check bits for the data in that column. The (n1−k1)×(n2−k2) region at the lower right of this block contains parity check bits for each of the n2−k2 columns above and for each of the n1−k1 rows to the left. Where, for example, a 64QAM configuration is adopted, k1=k2=57 and n1=n2=63. Because 57=26−6−1, the 7 conventional parity check bits can be replaced by 7 error check bits (Hamming, BCH, etc.), as discussed in S. B. Wicker, Error Control Systems, Prentice Hall, Englewood Cliffs NJ, 1995, pp. 8-11, 90-94 and elsewhere. Use of a QAM constellation is discussed by W. Tomasi, Electronic Communication Systems, Prentice Hall, Englewood Cliffs, NJ, 1988, pp. 503-527.
Use of a trellis construction for block and convolution codes allows an improvement in effective bit transfer rate, through a procedure discussed in some detail in S.B. Wicker, ibid., pp. 356-392. The procedure includes (1) insertion of a redundant bit for every m bits, (2) expansion of the signal constellation (e.g., QAM) from 2m to 2m+1 symbols, and (3) use of an (m+1)-bit encoded source block to specify a signal from the expanded constellation. However, construction of a trellis diagram for optimal BCH decoding has not been disclosed.
What is needed is an approach for constructing a simplified trellis diagram that is optimal for BCH decoding.